package com.zh.note.leetcode.greedy;

import java.util.*;

/**
 * 406. 根据身高重建队列
 */
public class LC_406_reconstructQueue {

    public int[][] reconstructQueue(int[][] people) {
        // 身高从大到小排（身高相同k小的站前面）
        Arrays.sort(people, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1]; // o2[1] - o1[1]是升序，故在a[0] == b[0]的情况下，会根据k值，升序排列
            } else {
                return o2[0] - o1[0];
            }

        });
        List<int[]> queue = new LinkedList<>();
        for (int[] p : people) {
            queue.add(p[1], p);//Linkedlist.add(index, value)，会將value插入到指定index里。
        }
        return queue.toArray(new int[people.length][]);
    }
}
